class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        //线性查找：时间复杂度O(n + m)，空间复杂度O(1)
        int nlen = matrix.size();  //matrix的行数
        if(0 == nlen)  return false;
        int mlen = matrix[0].size();  //列数
        //从矩阵右上角开始遍历排除
        int n = 0;
        int m = mlen - 1;

        while((n < nlen) && (m >= 0)){
            if(target == matrix[n][m]){
                return true;
            }else if(target > matrix[n][m]){
                n++;
            }else if(target < matrix[n][m]){
                m--;
            }else{
                return false;
            }
        }

        return false;
    }
};